////1.组队 V
//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//	cout<<490;
//} 

////2.年号子串 X
//#include <bits/stdc++.h>
//using namespace std;
//vector<int> v;
//int main()
//{
//	int n=2019;
//	while(n)
//	{
//		int ch=n%26;
//		v.push_back(ch);
//		n/=26;
//	}
//	reverse(v.begin(),v.end());
//	for(int i=0;i<v.size();i++)printf("%c ",v[i]+'A'-1); //记录余数，并且将余数从后往前输出,或者逆序后正向输出。 记住，不是sort，sort是将数组有序排序，我们要的是reverse 
//	return 0;
// } 

////3.数列求值 -大数加法 X
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e8+10;
//typedef long long ll;
//vector<vector<int>> a(N,vector<int>());//大数加法，里面的数据都是反着存的，打印的时候要逆着打印
//vector<int> add(vector<int> a,vector<int> b)
//{
//	if(a.size()<b.size())return add(b,a);
//	int t=0;//用于进位
//	vector<int> c;
//	for(int i=0;i<a.size();i++)
//	{
//		t+=a[i];
//		if(i<b.size())t+=b[i];
//		c.push_back(t%10);
//		t/=10;
//	}
//	while(c.back()==0&&c.size()>1)c.pop_back();
//	return c;
//}
//int main()
//{
//
//	for(int i=4;i<=22000000;i++)
//	{
//		vector<int> sum;
//		for(int j=i-3;j<=i-1;j++)
//		{
//			add(sum,a[j]);
//		}
//		a[i]=sum;
//	}
//	cout<<a[20190324];
//
//
////	vector<int> a(20,1);
////	vector<int> b(10,1);
////	vector<int> c=add(a,b);
////	reverse(c.begin(),c.end());
////	for(int i=0;i<c.size();i++)cout<<c[i];
//	return 0;
//}
//法2.只管后四位的加减计算，高位对低位没有影响。

//#include <bits/stdc++.h>
//using namespace std;
//const int N=22000000+10;
//typedef long long ll;
//int b[N];
//int main()
//{
//	int sum=0;
//	b[1]=1,b[2]=1,b[3]=1;
//	for(int i=4;i<=22000000;i++)
//	{
//		sum=0;
//		for(int j=i-3;j<=i-1;j++)
//		{
//			int c=b[j]%10000;
//			sum+=c;
//		}
//		b[i]=sum;
//	}
//	cout<<b[20190324]%10000;
//	return 0;
//}

////4.数的分解  V
//
//#include <iostream>
//using namespace std;
//bool isyes(int n)
//{
//	while (n)
//	{
//		int val = n % 10;
//		if (val == 2 || val == 4)return false;
//		n /= 10;
//	}
//	return true;
//}
//int main()
//{
//	int cnt = 0;
//	for (int i = 1; i <= 2019; i++)
//	{
//		if(isyes(i))
//		for (int j = i + 1; j <= 2019 - i; j++)
//		{
//			if (isyes(j))
//			{
//				int k = 2019 - i - j;
//				if (isyes(k)&&k>i&&k>j)cnt++;
//			}
//		}
//	}
//	cout << cnt;
//	return 0;
//} 

//5.迷宫 X
//#include <bits/stdc++.h>
//using namespace std;
//const int N=60;
//int gard[N][N];
//typedef pair<int,int> PII;
//queue<PII> q;
//vector<char> path;
//int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
//int st[N][N];
//void bfs(int x,int y)
//{
//	q.push({x,y});
//	st[x][y]=1;
//	PII t,tt;
//	int sz=1;

//6.特别数的和
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e4+10;
//bool isyes(int n)
//{
//	while(n)
//	{
//		int val=n%10;
//		if(val==2||val==0||val==1||val==9)return true;
//		n/=10;
//	}
//	return false;
//}
//int main()
//{
//	int n;
//	cin>>n;
//	int sum=0;
//	for(int i=1;i<=n;i++)
//	{
//		if(isyes(i))sum+=i;	
//	}
//	cout<<sum;
//	return 0;
// } 

//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e5+10;
//int a[N]; 
//
//queue<int> q;//装下标 
//int main()
//{
//	int n;
//	int depth=0;
//	cin>>n;
//	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
//	
//	int sz=1;
//	int max=0;
//	int begin=1,end=begin+sz-1;
//	q.push(1);
//	int maxidex=0;
//	while(!q.empty())
//	{
//		depth++;
//		int cnt=0;
//		int begin=q.front();
//		int end=begin+sz-1;
//		for(int i=begin;i<=end;i++)
//		{
//			cnt+=a[i]*depth;
//		}
//		if(cnt>max)
//		{
//			max=cnt;
//			maxidex=depth;
//		}
//
//		for(int i=begin;i<=end;i++)
//		{
//			if(2*i<=N)
//			q.push(2*i);
//
//			if(2*i+1<=N)
//			q.push(2*i +1);
//
//			q.pop();
//		}
//		sz=q.size();
//
//
//	}
//	cout<<maxidex;
//
//	return 0;
//}


